﻿#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;

typedef int SlDateType;
//静态顺序表,其特点是如果满了就不能再插入，给多大的空间很难确定
//给小了不够用，给大了容易浪费空间

//动态顺序表
typedef struct SeqList
{
	SlDateType* a;  //指向数组的空间的首地址,动态版本
	int size;  //表示数组中有多少个数据
	int capacity; //表示数组实际能存数据的空间容量有多大
}SL;

//打印顺序表
void SeqListPrint(SL* ps);

//接口函数--命名风格根据STL
void SeqListInit(SL*ps);

//释放动态申请的内存空间
void SeqListDestory(SL* ps);

//检查空间是否满了
void SeqListCheckCapacity(SL* ps);

//尾插入数据
void SeqListPushBack(SL* ps, SlDateType x);

//尾删除数据
void SeqListPopBack(SL* ps);

//头插入数据
void SeqListPushFront(SL* ps, SlDateType x);

//头删除数据
void SeqListPopFront(SL* ps);

//返回x数据的下标，若没有数据则返回-1
SlDateType SeqListFind(SL* ps, SlDateType x);

//在指定的pos下标位置插入数据
void SeqListInsert(SL* ps, int pos, SlDateType x);

//在指定的pos下标删除数据
void SeqListErase(SL* ps, int pos);

//顺序表的缺陷
//1.空间不够了需要增容，扩容有代价
//2.为了减少扩容的代价，一般扩容扩大两倍，这样可能会导致浪费一定的空间
//3.顺序表要求从头位置开始存储，如果我们从头部或者中间开始插入或者删除数据就要挪动数据，效率低

//针对顺序表的缺陷，可以设计链表